G题被K=1安排
怀疑人生
A
- 裸的最大流最小割定理
- 正确的模板即可
B
- 签到又又又崩了
- 签到崩盘率高达100%
C
- 预处理dfs全排列36种
- 从小到大暴力匹配即可、
- 1A
D
题意
题解
E
题意
题解
F
题意
题解
G
- SB题
H
题意
题解
I
题意
题解
J
- dfs爆搜时间复杂度爆炸(但现场数据水，没准还能过呢，笑
- 正解：定义dp[i]:数字选择状态为i的方案数，预处理每个背包的情况
- 转移：一个显然的转移时dp[i]由两个i小的状态转移而来，但这样是错的，因为这两个状态可能这样暴力转移的时间复杂度为$O(2^{2n})$，看起来好像过不了的样子
- 一个转移的优化，从小到大枚举状态i，用总状态减去当前状态i，则
1
2
3
4
5
6
7
8
9- 转移代码
```c++
for(int i=1;i<(1<<n);i++){
int k=(1<<n)-1-i;
for(int j=k;;j=(j-1)&k){
dp[i|j]+=dp[i]*f[j];
if(j==0)break;
}
}